package oj;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

/**
 * @author chaolong.jin
 * @description
 * @date 2019/08/24 17:13
 */
public class HeapSort {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int n = scanner.nextInt();
            int[] a = new int[n];

            for (int i = 0; i < n; i++) {
                a[i] = new Random().nextInt(100);
                System.out.print(a[i] + " ");
            }
            for (int i = (n - 1) >> 1; i >= 0; i--) {
                buildHeap(a, i, n - 1);
            }
            for (int i = n - 1; i >= 0; i--) {
                swap(a, 0, i);
                buildHeap(a, 0, i - 1);
            }
            System.out.println();
            System.out.println(Arrays.toString(a));
        }
    }

    private static void buildHeap(int[] a, int index, int length) {
        int li = (index << 1) + 1;
        int ri = li + 1;
        if (li > length) {
            return;
        }
        int max = li;
        if (ri <= length && a[li] < a[ri]) {
            max = ri;
        }
        if (a[max] > a[index]) {
            swap(a, max, index);
            buildHeap(a, max, length);
        }
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
